package com.搜索和回溯;


class Solution10 {
//    //法一：先序+求深度判断
//    public boolean isBalanced(TreeNode root) {
//        if(root==null) return true;//特殊情况判断
//        return Math.abs(depth(root.left)-depth(root.right))<=1 && isBalanced(root.left) && isBalanced(root.right);
//    }
//    int depth(TreeNode root){
//        if(root==null) return 0;
//        int leftDepth=depth(root.left);
//        int rightDepth=depth(root.right);
//        return Math.max(leftDepth,rightDepth)+1;
//    }

    //法二：后序+剪枝判断（即在后序遍历中直接判断）
    public boolean isBalanced(TreeNode root) {
        return recur(root)!=-1;
    }
    int recur(TreeNode root){
        //终止条件
        if(root==null) return 0;
        //递推
        int leftDepth=recur(root.left);
        if(leftDepth==-1) return -1;//如果左子数已经是不平衡的，则直接返回不平衡
        int rightDepth=recur(root.right);
        if(rightDepth==-1) return -1;//如果右子数已经是不平衡的，则直接返回不平衡
        //返回值
        //如果左子数-右子数的绝对值小于等于1，则返回该节点的深度，否则返回-1，代表不平衡。
        return Math.abs(leftDepth-rightDepth)<=1?Math.max(leftDepth,rightDepth)+1:-1;
    }
}

public class 剑指Offer55II平衡二叉树 {
    public static void main(String[] args) {

    }
}
